import java.util.Arrays;

public class Code1 {
    // 最长数对链

    public int findLongestChain(int[][] pairs) {

        // 在填写 dp 表时，对于数据的获取我们必须要遵守一个固定的顺序。
        // 但是在 pairs 数组中（以示例二为依据）当选择到 第二个 元素时，既可以与前一个数据进行连接，也可以和后一个数据进行连接。很显然是存在问题的
        // 所以在书写代码前进行预处理操作
        // 我们假设 [a,b] [c,d] 要做到填表时只向前获取数据，就需要确保 a < d
        // 又知道在每一个数对链中，数据都是严格递增的，此时针对数对中第一个数进行排序，做到 a < c 又因为 数对链中 c < d 以此我们就可以达到 a < d 的操作
        // 这里是一个 arrays 中的一个排序方法，这里是根据第一个位置进行从小到大排序
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);

        // 创建 dp 表
        // dp[i] 表示：以 i 位置元素为结尾的所有数对链中，最长的数对链长度
        int n = pairs.length;
        int[] dp = new int[n];

        // 初始化操作
        // 同样的，通过分析可以将数据分为两部分
        // 一种为 i 单独作为一个长度，记录为 1
        // 另一种为 i 之前的元素长度(dp[j])与 i 进行连接后 dp[j] + 1 的操作
        // 这里初始化为最坏的情况，全部初始化为 1
        for(int i = 0; i < n; i++){
            dp[i] = 1;
        }

        // 进行填表操作
        // 从左向右
        int ret = 1;
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                // 这里要确保 p[i 之前的元素][1] < p[i][0] 才能连接到前面，长度才能 + 1
                if(pairs[j][1] < pairs[i][0]){
                    dp[i] = Math.max(dp[j]+1, dp[i]);
                }
            }
            ret = Math.max(ret, dp[i]);
        }
        // 返回值要确保获取到的是 dp 表中的最大值
        return ret;
    }
}
